package com.lwl.Algorithmic_data_structure.堆与堆排序.mycode;

import com.lwl.Utils.NumberUtils;

/**
 * 最大堆,这个堆会存在一个问题，就是如果堆内的某一个对象（现在是int，正常应该是泛型）发生变化之后堆不会做出调整
 */
public class MaxHeap {
    private int[] heap;
    private int heapSize;
    private final int maxSize;

    public MaxHeap(int maxSize)
    {
        heap = new int[maxSize];
        this.maxSize = maxSize;
    }

    public void push(int value)
    {
        if (heapSize == maxSize)
        {
            throw new RuntimeException("超出堆的Size了。。。");
        }
        heap[heapSize] = value;
        heapFloat(heap,heapSize++);
    }

    public int pop()
    {
        if (heapSize == 0)
        {
            throw new RuntimeException("当前堆为空。。。");
        }
        int res = heap[0];
        NumberUtils.swap(heap,0,--heapSize);
        heapSinking(heap,0,heapSize);
        return res;
    }

    /**
     *  指定任一位置开始下沉操作
     */
    private void heapSinking(int[] heap, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize)
        {
            int largeSon = left + 1 < heapSize && heap[left] < heap[left + 1] ? left + 1 : left;
            if (heap[largeSon] < heap[index])
            {
                break;
            }
            NumberUtils.swap(heap,index,largeSon);
            index = largeSon;
            left = index * 2 + 1;
        }
    }


    /**
     * 在堆末尾插入新值后进行上浮操作
     * 也不一定是堆尾，可以指定任一index位置进行上浮操作
     */
    private void heapFloat(int[] heap, int index)
    {
        while (heap[index] > heap[(index - 1)/2])
        {
            NumberUtils.swap(heap,index,(index - 1)/2);
            index = (index - 1)/2;
        }
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.push(100);
        maxHeap.push(98);
        maxHeap.push(99);
        System.out.println(maxHeap.pop());
        System.out.println(maxHeap.pop());
        System.out.println(maxHeap.pop());
    }
}
